package leetcode.dynamic;

public class Lc5 {


    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[s.length()][s.length()];
        int l = 0, r = 0, maxlen = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i - 1] ) ) {
                    dp[j][i] = true;
                    if (i - j + 1 > maxlen) {
                        maxlen = i - j + 1;
                        l = j;
                        r = i;
                    }
                }
            }
        }
        return s.substring(l, r + 1);
    }


    public String longestPalindrome2(String s) {

        int n = s.length();
        boolean[][] dp = new boolean[n + 1][n + 1];
        int l = 0, r = 0;
        int max = 0;
        for (int i = n - 1; i >= 0 ; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (max < j - i) {
                        max = j - i;
                        l = i;
                        r = j;
                    }
                }
            }
        }
        return s.substring(l, r + 1);
    }

    public static void main(String[] args) {
        Lc5 lc5 = new Lc5();
        System.out.println(lc5.longestPalindrome("cccc"));
    }
}
